#include <iostream>
#include <fstream>
#include <cctype>
#include <string>
#include <map>
#include <list>
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <sstream>
#include <math.h>


using namespace std;

void print_vals();

void get_frequency();

void init_probs(bool is_rand);

void calc_prob_v_n();

double prob_cluster_given_pair(int c, string v, string n);

double calc_norm_cluster(int clusterNum);

void calc_all_c_given_vn();

int find_num_clust();

void fnc_noun(string word, map<string, double>* awn_pointer, map<string, double>* awv_pointer, map<string, bool>* twn_pointer, map<string, bool>* twv_pointer, double count);

void fnc_verb(string word, map<string, double>* awn_pointer, map<string, double>* awv_pointer, map<string, bool>* twn_pointer, map<string, bool>* twv_pointer, double count);

void evaluate();

map<string, double> counts;
map<string, double> verbs;
map<string, double> nouns;
map<string, double> clusters;
map<string, double> pair_prob;
map<string, double> c_given_vn;
map<string, double> all_words_nouns;
map<string, double> all_words_verbs;

map<string, list<string> > verbs_adj_list; //key = verb, value = list of nouns seen with verb
map<string, list<string> > nouns_adj_list; //key = noun, value = list of verbs seen with noun


int num_clust = 0;
int num_of_pairs = 0;
int num_iterations = 1500;
int iterations_before_print = 101;

bool print_nv = false;
int nv_size = 1000;

string datafile = "./data/wsj_within_1.txt";

int main(int argc, char *argv[]){
  srand( time(NULL) );
  get_frequency();
  num_clust = find_num_clust();
  cout << "Number of clusters: " << num_clust << endl;
  num_clust = 10;
  bool is_rand = true;
  init_probs(is_rand);
  evaluate();
  print_nv = true;
  print_vals();


  

  
  /*
  get_frequency();

  string str = "point;has";
  cout << counts[str] << endl;
  */

  /*
  string s = "";
  int tot = 42;
  stringstream oss;
  oss << s << tot << '\n';
  cout << oss.str();
  */

  /*
  double sum = 0;
  for (int i = 0; i < num_clust; i++){
    sum += calc_norm_cluster(i);
  }
  cout << sum/static_cast<double>(num_of_pairs) << endl;
  */


  /*  
  double sum;
  for (int i = 0; i < num_clust; i++){
    string s = "";
    stringstream ss;
    
    ss << s << i << ";" << "review;was";
    double temp = c_given_vn[ss.str()];
    cout << temp << endl;
    sum += temp;
  }
  cout << sum << endl;
  */

  /*
  map<string, double>::iterator it;
  double sum = 0;
  for (it = pair_prob.begin(); it != pair_prob.end(); it++){
    sum += it->second;
  }
  cout << sum << endl;
  */
  /*
  for (int i = 0; i < num_clust; i++) {
    map<string, list<string> >::iterator it;
    double sum = 0;
    for (it = verbs_adj_list.begin(); it != verbs_adj_list.end(); it++){
      string s = "";
      stringstream ss;

      ss << s << it->first << ";" << i;

      sum += verbs[ss.str()];
    }
    string s = "";
    stringstream ss;
    ss << s << i;
    cout << "Verb Cluster " << i << " sum: "<< sum << endl;
    cout << "Verb Cluster: " << clusters[ss.str()] << endl; 
  }

  for (int i = 0; i < num_clust; i++) {
    map<string, list<string> >::iterator it;
    double sum = 0;
    for (it = nouns_adj_list.begin(); it != nouns_adj_list.end(); it++){
      string s = "";
      stringstream ss;

      ss << s << it->first << ";" << i;

      sum += nouns[ss.str()];
    }
    string s = "";
    stringstream ss;
    ss << s << i;
    cout << "Noun Cluster " << i << " sum: "<< sum << endl;
    cout << "Noun Cluster: " << clusters[ss.str()] << endl; 
  }
  */
  // Check that clusters sum to 1
  /*
  double sum = 0;
  for (int i = 0; i < num_clust; i++){
    string s = "";
    stringstream ss;
    ss << s << i;
    sum += clusters[ss.str()];
  }
  cout << sum << endl;
  */

  return 0;
}

void print_vals(){
  for (int z = 0; z < num_clust; z++){
  
    cout << "\n\n--------------------\nCluster " << z << ":\n--------------------\nNOUNS:\n-----\n";
    
    map<string, double> temp;
    map<string, double>::iterator it2;
    map<string, list<string> >::iterator it;

    for (it = nouns_adj_list.begin(); it != nouns_adj_list.end(); it++){
      string s = "";
      stringstream ss;
      ss << s << it->first << ";" << z;
      temp[it->first] = nouns[ss.str()];
      if (temp.size() > 20){
	double min = 2;
	bool found_first = false;
	string min_key = "";
	int count1 = 0;
	int count2 = 0;
	for (it2 = temp.begin(); it2 != temp.end(); it2++){
	  count1++;
	  if (it2->second < min || not found_first){
	    found_first = true;
	    min = it2->second;
	    min_key = it2->first;
	  }
	  else{
	    count2++;
	  }
	}
	if (count1 == count2){
	  cout << "bad\n";
	}
	it2 = temp.find(min_key);
	temp.erase(it2);
      }
    }
    string s_c = "";
    stringstream ss_c;
    ss_c << s_c << z;
    for (it2 = temp.begin(); it2 != temp.end(); it2++){
      cout << it2->first << "; " << it2->second/clusters[ss_c.str()] << endl;
    }
  
    cout << "\nVERBS:\n-----\n";
    temp.clear();
    for (it = verbs_adj_list.begin(); it != verbs_adj_list.end(); it++){
      string s = "";
      stringstream ss;
      ss << s << it->first << ";" << z;
      temp[it->first] = verbs[ss.str()];
      if (temp.size() > 20){
	double min = 2;
	bool found_first = false;
	string min_key = "";
	for (it2 = temp.begin(); it2 != temp.end(); it2++){
	  if (it2->second < min || not found_first){
	    found_first = true;
	    min = it2->second;
	    min_key = it2->first;
	  }
	}
	it2 = temp.find(min_key);
	temp.erase(it2);
      }
    }
    string s_c2 = "";
    stringstream ss_c2;
    ss_c2 << s_c2 << z;
    for (it2 = temp.begin(); it2 != temp.end(); it2++){
      cout << it2->first << "; " << it2->second/clusters[ss_c2.str()] << endl;
    }
  }

  cout << "\nCLUSTERS:\n-----\n";
  map<string, double>::iterator it;
  for (it = clusters.begin(); it != clusters.end(); it++){
    cout << it->first << "; " << it->second << endl;
  } 
}

void get_frequency(){
  map<string, double>::iterator it;
  string n;
  string v;
  string noun;
  string verb;
  fstream instream;
  instream.open(datafile.c_str());
  
  int count = 0;
  instream >> n;
  instream >> v;
  std::transform(n.begin(), n.end(), n.begin(), ::tolower);
  std::transform(v.begin(), v.end(), v.begin(), ::tolower);

  while(instream.good()){    
    count++;
    
    string str = n + ";" + v;

    it = counts.find(str);
    if (it == counts.end()){
      counts[str] = 1;
      verbs_adj_list[v].push_front(n);
      nouns_adj_list[n].push_front(v);
    }
    else {
      counts[str] += 1;
    }
    instream >> n;
    instream >> v;
    std::transform(n.begin(), n.end(), n.begin(), ::tolower);
    std::transform(v.begin(), v.end(), v.begin(), ::tolower);

  }
  
  num_of_pairs = count;

  instream.close();
}

void init_probs(bool is_rand){
  int clust_total = 0;
  string n;
  string v;
  map< int, int > noun_total;
  map< int, int > verb_total;
  for (int i = 0; i < num_clust; i++){
    string s_c = "";
    stringstream oss_c;
    oss_c << s_c << i;
    double temp = rand()%1000;
    clusters[oss_c.str()] = static_cast<double>(temp);
    clust_total += temp;
    map<string, list<string> >::iterator it_m;
    list<string>::iterator it_l;
    if (nouns_adj_list.empty() || verbs_adj_list.empty()){
      cout << "Here is the bug!!\n";
    }
    for (it_m = nouns_adj_list.begin(); it_m != nouns_adj_list.end(); it_m++){
      n = it_m->first;
      string s_n = "";
      stringstream oss_n;
      oss_n << s_n << n << ";" << i;
	
      map<string, double>::iterator it_d;
      it_d = nouns.find(oss_n.str());
      if (it_d == nouns.end()){
	if(is_rand || i == all_words_nouns[n]){
	  temp = rand()%1000;
	}
	else{
	  temp = 0.0000000001;
	}
	nouns[oss_n.str()] = static_cast<double>(temp);
	noun_total[i] += temp;
      }
    }

    for (it_m = verbs_adj_list.begin(); it_m != verbs_adj_list.end(); it_m++){
      v = it_m->first;
      string s_v = "";
      stringstream oss_v;
      oss_v << s_v << v << ";" << i;

      map<string, double>::iterator it_d;
      it_d = verbs.find(oss_v.str());
      if (it_d == verbs.end()){
	/*
	if (is_rand || i == all_words_verbs[v]){
	  temp = rand()%1000;
	}
	*/
	if (i > 5){
	  temp = rand()%1000;
	}
	else if (v != "is" && v != "was" && v != "has" && v != "have" && v != "are" && v != "haven't" && v != "be" && v != "made" && v != "make" && v != "makeing" && v != "been" && v != "did" && v != "had" && v != "said" && v != "say" && v != "'re" && v != "'s" && v != "got" && v != "come" && v != "came" && v != "do" && v != "were" && v != "does" && v != "doing" && v != "done") {
	  temp = rand()%1000;
	}
	else {
	  temp = 0;
	}
	verbs[oss_v.str()] = static_cast<double>(temp);
	verb_total[i] += temp;
      }
    }
  }

  for (int i = 0; i < num_clust; i++){
    string s = "";
    stringstream oss;
    oss << s << i;
    clusters[oss.str()] /= static_cast<double>(clust_total);
  }
  map<string, list<string> >::iterator it_m;
  for (it_m = nouns_adj_list.begin(); it_m != nouns_adj_list.end(); it_m++){
    for (int i = 0; i < num_clust; i++){
      string s = "";
      string s2 = "";
      stringstream ss;
      stringstream ss2;
      ss << s << it_m->first << ";" << i;
      ss2 << s2 << i;
      if (noun_total[i] == 0){
	cout << "bad\n";
      }
      nouns[ss.str()] = clusters[ss2.str()]*nouns[ss.str()]/static_cast<double>(noun_total[i]);
    }
  }
  for (it_m = verbs_adj_list.begin(); it_m != verbs_adj_list.end(); it_m++){
    for (int i = 0; i < num_clust; i++){
      string s = "";
      string s2 = "";
      stringstream ss;
      stringstream ss2;
      ss << s << it_m->first << ";" << i;
      ss2 << s2 << i;
      verbs[ss.str()] = clusters[ss2.str()]*verbs[ss.str()]/static_cast<double>(verb_total[i]);
    }
  }
}

void calc_prob_v_n(){

  /*
  map<string, list<string> >::iterator it_n;
  map<string, list<string> >::iterator it_v;

  for(it_n = nouns_adj_list.begin(); it_n != nouns_adj_list.end(); it_n++){
    for(it_v = verbs_adj_list.begin(); it_v != verbs_adj_list.end(); it_v++){
      string n = it_n->first;
      string v = it_v->first;

      string nv = "";
      stringstream ss_nv;
    
      ss_nv << nv << n << ";" << v;
      
      double prob = 0;
      
      for (int i = 0; i < num_clust; i++){
	string nc = "";
	string vc = "";
	string c = "";
	stringstream ss_nc;
	stringstream ss_vc;
	stringstream ss_c;
      
	ss_nc << nc << n << ";" << i;
	ss_vc << vc << v << ";" << i;
	ss_c << c << i;
      
	prob += verbs[ss_vc.str()]*nouns[ss_nc.str()]/clusters[ss_c.str()];
      }

      
      pair_prob[ss_nv.str()] = prob;
      
      
    }
  }
  */

  string n;
  string v;

  map<string, list<string> >::iterator it_m;
  list<string>::iterator it_l;
  for (it_m = nouns_adj_list.begin(); it_m != nouns_adj_list.end(); it_m++){
    n = it_m->first;
    for (it_l = it_m->second.begin(); it_l != it_m->second.end(); it_l++){
      v = *it_l;
      double prob = 0;

      string nv = "";
      stringstream ss_nv;
    
      ss_nv << nv << n << ";" << v;
      
      for (int i = 0; i < num_clust; i++){
	string nc = "";
	string vc = "";
	string c = "";
	stringstream ss_nc;
	stringstream ss_vc;
	stringstream ss_c;
	
	ss_nc << nc << n << ";" << i;
	ss_vc << vc << v << ";" << i;
	ss_c << c << i;
      
	prob += verbs[ss_vc.str()]*nouns[ss_nc.str()]/clusters[ss_c.str()];
      }
      pair_prob[ss_nv.str()] = prob;
    }
  }
}


double prob_cluster_given_pair(int c, string v, string n){
  double numerator = 1;
  string nc = "";
  string vc = "";
  string s_c = "";
  string nv = "";
  stringstream ss_nc;
  stringstream ss_vc;
  stringstream ss_c;
  stringstream ss_nv;

  ss_nc << nc << n << ";" << c;
  ss_vc << vc << v << ";" << c;
  ss_c << s_c << c;
  ss_nv << nv << n << ";" << v;

  numerator *= nouns[ss_nc.str()]*verbs[ss_vc.str()]/clusters[ss_c.str()];

  return numerator/pair_prob[ss_nv.str()];
  
}

void calc_all_c_given_vn(){
  string n;
  string v;
  
  c_given_vn.clear();

  map<string, list<string> >::iterator it_m;
  list<string>::iterator it_l;
  for (it_m = nouns_adj_list.begin(); it_m != nouns_adj_list.end(); it_m++){
    n = it_m->first;
    for (it_l = it_m->second.begin(); it_l != it_m->second.end(); it_l++){
      v = *it_l;
      for (int i = 0; i < num_clust; i++){
	string cnv = "";
	stringstream ss_cnv;
	
	ss_cnv << cnv << i << ";" << n << ";" << v;
	map<string, double>::iterator it;
	it = c_given_vn.find(ss_cnv.str());
	if (it != c_given_vn.end()){
	  continue;
	}
	c_given_vn[ss_cnv.str()] = prob_cluster_given_pair(i, v, n);
      }		 
    }
  }
}

double calc_norm_cluster(int clusterNum) {
  map <string, double>::iterator countItr;

  double sum = 0;
  for (countItr = counts.begin(); countItr != counts.end(); countItr++) {
    string s = "";
    stringstream ss;
    ss << s << clusterNum << ";" << countItr->first;
    sum += static_cast<double>(countItr->second) * c_given_vn[ss.str()];
  }
  return sum;
}

void evaluate(){
  double max_change = 100;
  int k = 0;
  double old_clusters[num_clust];
  double normalizers[num_clust];
  while (max_change > .000001 && k < num_iterations){
    k += 1;
    max_change = 0;
    double count = 0;
    cout << "Iteration #: " << k << endl;
    calc_prob_v_n();
    calc_all_c_given_vn();
    for (int i = 0; i < num_clust; i++){
      string c = "";
      stringstream ss_c;
      ss_c << c << i;
      old_clusters[i] = clusters[ss_c.str()];
      normalizers[i] = calc_norm_cluster(i);
    }
    for (int i = 0; i < num_clust; i++){
      double normalizer = normalizers[i];
      string c = "";
      stringstream ss_c;
      ss_c << c << i;
      double temp = normalizer/static_cast<double>(num_of_pairs) - clusters[ss_c.str()];
      if (max_change < temp){
	max_change = temp;
      }
      count += 1;
      clusters[ss_c.str()] = normalizer/static_cast<double>(num_of_pairs);
      old_clusters[i] = clusters[ss_c.str()];

      map<string, list<string> >::iterator it_l;
      for (it_l = nouns_adj_list.begin(); it_l != nouns_adj_list.end(); it_l++){
	double sum = 0;
	list<string>::iterator it_s;

	string n = it_l->first;

	for (it_s = it_l->second.begin(); it_s != it_l->second.end(); it_s++){
	  string v = *it_s;
	  
	  string nv = "";
	  string cnv = "";
	  stringstream ss_nv;
	  stringstream ss_cnv;

	  ss_nv << nv << n << ";" << v;
	  ss_cnv << cnv << i << ";" << n << ";" << v;

	  sum += counts[ss_nv.str()]*c_given_vn[ss_cnv.str()];
	}
	
	string nc = "";
	stringstream ss_nc;
	ss_nc << nc << n << ";" << i;

	temp = old_clusters[i]*sum/normalizer - nouns[ss_nc.str()];
	if (max_change < temp){
	  max_change = temp;
	}
	count += 1;
	nouns[ss_nc.str()] = old_clusters[i]*sum/normalizer;
      }
      for (it_l = verbs_adj_list.begin(); it_l != verbs_adj_list.end(); it_l++){
	double sum = 0;
	list<string>::iterator it_s;

	string v = it_l->first;

	for (it_s = it_l->second.begin(); it_s != it_l->second.end(); it_s++){
	  string n = *it_s;
	  
	  string nv = "";
	  string cnv = "";
	  stringstream ss_nv;
	  stringstream ss_cnv;

	  ss_nv << nv << n << ";" << v;
	  ss_cnv << cnv << i << ";" << ss_nv.str();
	  
	  sum += counts[ss_nv.str()]*c_given_vn[ss_cnv.str()];
	}
	
	string vc = "";
	stringstream ss_vc;
	ss_vc << vc << v << ";" << i;
	temp = old_clusters[i]*sum/normalizer - verbs[ss_vc.str()];
	if (max_change < temp){
	  max_change = temp;
	}
	count += 1;
	verbs[ss_vc.str()] = old_clusters[i]*sum/normalizer;
      }
    }
    cout << "Max Change = " << max_change << endl;
    if (k > 0 && k%iterations_before_print == 0){
      print_vals();
    }
  }
}

int find_num_clust(){
  double count = 0;
  map<string, bool> test_words_nouns;
  map<string, bool> test_words_verbs;
  map<string, list<string> >::iterator it_m;
  list<string>::iterator it_l;
  for (it_m = nouns_adj_list.begin(); it_m != nouns_adj_list.end(); it_m++){
    all_words_nouns[it_m->first] = -1;
    test_words_nouns[it_m->first] = true;
    for (it_l = it_m->second.begin(); it_l != it_m->second.end(); it_l++){
      all_words_verbs[*it_l] = -1;
      test_words_verbs[*it_l] = true;
    }
  }
  while (not test_words_nouns.empty()){
    string word = test_words_nouns.begin()->first;
    all_words_nouns[word] = count;
    test_words_nouns.erase(word);
    fnc_noun(word, &all_words_nouns, &all_words_verbs, &test_words_nouns, &test_words_verbs, count);

    count += 1;
  }
  return count;
}

void fnc_noun(string word, map<string, double>* awn_pointer, map<string, double>* awv_pointer, map<string, bool>* twn_pointer, map<string, bool>* twv_pointer, double count){
  list<string>::iterator it_l;
  for (it_l = nouns_adj_list[word].begin(); it_l != nouns_adj_list[word].end(); it_l++){
    if (twv_pointer->find(*it_l) != twv_pointer->end()){
      (*awv_pointer)[*it_l] = count;
      twv_pointer->erase(*it_l);
      fnc_verb(*it_l, awn_pointer, awv_pointer, twn_pointer, twv_pointer, count);
    }
  }
}

void fnc_verb(string word, map<string, double>* awn_pointer, map<string, double>* awv_pointer, map<string, bool>* twn_pointer, map<string, bool>* twv_pointer, double count){
  list<string>::iterator it_l;
  for (it_l = verbs_adj_list[word].begin(); it_l != verbs_adj_list[word].end(); it_l++){
    if (twn_pointer->find(*it_l) != twn_pointer->end()){
      (*awn_pointer)[*it_l] = count;
      twn_pointer->erase(*it_l);
      fnc_noun(*it_l, awn_pointer, awv_pointer, twn_pointer, twv_pointer, count);
    }
  }
}

/*
double round(double num, int precision);

double round(double num, int precision){
  int orderOfMagnitude = pow(10,precision);
  return (static_cast<double>(int(num* orderOfMagnitude + 0.5))/orderOfMagnitude);
}
 */











